The present invention relates to techniques for analyzing a body of data, such as data defining an image or another signal. More specifically, the invention relates to techniques that produce results indicating overall attributes of extended subsets of a body of data.
A number of techniques have been proposed for producing results indicating attributes of a body of data.
Tanimoto et al., U.S. Pat. No. 4,622,632, describe a pyramidal array of processors that can operate on a pyramidal hierarchical data structure with a number of image resolution levels. FIG. 1 shows such a data structure in which the neighborhood of each unit cell includes four unit cells on the next lower level, and in the pyramidal processing system of FIG. 2 a data element corresponds exactly with a unit cell in the pyramidal data structure. For each unit cell, the pyramidal processing unit comprises registers, a virtual processor, and external storage. The neighborhood of a cell and relationships within neighborhoods are described at cols. 5-6. The association of actual and virtual processors and communication between processors is described in relation to FIGS. 3-5b. Control of the pyramidal processing unit and matching operations are described in relation to FIGS. 11-13a.
Miller, R., and Stout, Q. F., "Simulating Essential Pyramids," IEEE Transactions on Computers, Vol. 37, No. 12, December 1988, pp. 1642-1648, describe pyramid techniques that are useful when an image contains multiple objects of interest. These techniques simulate a separate "essential" pyramid over each object. FIG. 1 shows a standard pyramid computer, while FIG. 5 illustrates an essential pyramid, defined at pages 1644-1645. Implementations of essential pyramids are described at pages 1645-1646.
Conventional multigrid image processing techniques are also hierarchical, employing substantially fewer processing units at each level than at the next lower level. Frederickson, P. O., and McBryan, O. A., "Parallel Superconvergent Multigrid," Multigrid Methods: Theory, Applications and Supercomputing, McCormick, Marcel-Dekker, April 1988, pp. 195-210, describe a parallel superconvergent multigrid (PSMG) algorithm for the solution of large sparse linear systems on massively parallel supercomputers. Section 2.1 describes the use of the PSMG algorithm for a discretization problem by constructing two coarse grid solutions and combining them to provide a fine grid correction that is better than the coarse grid solutions. If the number of processors on a massively parallel machine is comparable to the number of fine grid points, the two coarse grid solutions can be solved simultaneously. For a problem in d dimensions, 2d coarse grids are obtained and the fine grid solution is defined by performing a suitable linear interpolation of the coarse grid points. This technique therefore obtains more results at each level of the hierarchy.
Kent, U.S. Pat. No. 4,601,055, describes an iconic-to-iconic low-level image processor with a sequence of identical intermediate stages between an input stage and an output stage, as shown and described in relation to FIG. 1. As shown in FIGS. 1-3, forward, recursive, and retrograde paths allow various operations, including forward and retrograde neighborhood operators. A discussion of the neighborhood operator begins at col. 6 line 42, and FIG. 5 illustrates the neighborhood operators, path functions, and combining logic for a plurality of neighborhood operations. A region of interest operator is described beginning at col. 13, line 48. The discussion beginning at col. 13, line 59 explains how the processor can construct multiresolution, pyramid, sequences of images by sampling and pixel doubling, and an example of pyramid-based processing is described in relation to FIG. 9.